package com.yun.algorithmproblem.leetcode;

/**
 * 2552. 统计上升四元组
 * <p>
 * 给你一个长度为 n 下标从 0 开始的整数数组 nums ，它包含 1 到 n 的所有数字，请你返回上升四元组的数目。
 * <p>
 * 如果一个四元组 (i, j, k, l) 满足以下条件，我们称它是上升的：
 * <p>
 * 0 <= i < j < k < l < n 且
 * nums[i] < nums[k] < nums[j] < nums[l] 。
 *
 * @author WY
 */
public class Leetcode2552 {

    public static void main(String[] args) {
        int[] nums = new int[]{1, 3, 2, 4, 5};
        Leetcode2552 obj = new Leetcode2552();
        long res = obj.countQuadruplets(nums);
        System.out.println(res);
    }

    /**
     * 仅仅击败20%
     */
    public long countQuadruplets1(int[] nums) {
        int length = nums.length;
        long res = 0;
        int[][] more = new int[length][length];
        int[][] less = new int[length][length];
        for (int i = 0; i < length; i++) {
            if (nums[length - 1] > nums[i]) {
                more[i][length - 1] = 1;
            }
        }
        for (int i = 0; i < length; i++) {
            for (int j = length - 2; j > i; j--) {
                if (nums[j] > nums[i]) {
                    more[i][j] = more[i][j + 1] + 1;
                } else {
                    more[i][j] = more[i][j + 1];
                }
            }
        }
        for (int i = 0; i < length; i++) {
            if (nums[i] > nums[0]) {
                less[i][0] = 1;
            }
        }
        for (int i = 1; i < length; i++) {
            for (int j = 1; j < i; j++) {
                if (nums[j] < nums[i]) {
                    less[i][j] = less[i][j - 1] + 1;
                } else {
                    less[i][j] = less[i][j - 1];
                }
            }
        }
        for (int j = 1; j < length - 2; j++) {
            for (int k = j + 1; k < length - 1; k++) {
                if (nums[j] > nums[k]) {
                    res += (long) less[k][j] * more[j][k];
                }
            }
        }
        return res;
    }

    public long countQuadruplets(int[] nums){

        return 0;
    }
}
